package com.rw.tool.util.expression;

import com.rw.tool.util.expression.element.Calculation;
import com.rw.tool.util.expression.element.ExpressionElement;
import com.rw.tool.util.expression.element.LeftParentheses;
import com.rw.tool.util.expression.element.NumberElement;
import com.rw.tool.util.expression.element.RightParentheses;
import com.rw.tool.util.expression.expression.Expression;
import com.rw.tool.util.expression.expression.InfixExpression;
import com.rw.tool.util.expression.expression.PostfixExpression;
import com.rw.tool.util.expression.expression.PrefixExpression;
import com.rw.tool.util.expression.expression.tree.ElementNode;

import java.util.LinkedList;
import java.util.List;

/**
 * 中缀表达式工具类
 */
public class ExpressionUtil {
    /**
     * 其它表达式转化为中缀表达式
     */
    public static InfixExpression ToInfix(Expression expression) {
        return new InfixExpression(ToPrefixOrPostfix(expression.getRootNode(), ExpressionType.INFIX));
    }

    /**
     * 其它表达式转化为后缀表达式
     */
    public static PostfixExpression ToPostfix(Expression expression) {
        return new PostfixExpression(ToPrefixOrPostfix(expression.getRootNode(), ExpressionType.POSTFIX));
    }

    /**
     * 其它表达式转化为前缀表达式
     */
    public static PrefixExpression ToPrefix(Expression expression) {
        return new PrefixExpression(ToPrefixOrPostfix(expression.getRootNode(), ExpressionType.PREFIX));
    }

    /**
     * 根据根节点，遍历出对应的表达式
     */
    private static List<ExpressionElement> ToPrefixOrPostfix(ElementNode node, ExpressionType type) {
        List<ExpressionElement> result = new LinkedList<>();
        // 如果该节点没有子节点，直接返回
        if (node.isChild()) {
            result.add(node.getElement());
            return result;
        }

        // 根据不同的表达式，做出不同的遍历
        switch (type) {
            case PREFIX:
                // 前缀表达式前序遍历
                result.add(node.getElement());
                result.addAll(ToPrefixOrPostfix(node.getLeftNode(), type));
                result.addAll(ToPrefixOrPostfix(node.getRightNode(), type));
                break;
            case INFIX:
                // 中缀表达式中序遍历
                List<ExpressionElement> left = ToPrefixOrPostfix(node.getLeftNode(), type);
                List<ExpressionElement> right = ToPrefixOrPostfix(node.getRightNode(), type);

                // 如果左边的表达式优先度较低，则对左边的表达式加上括号
                if (getPriority(node.getLeftNode().getElement()) < getPriority(node.getElement())) {
                    addParentheses(left);
                }

                // 右边的表达式情况较为复杂一些
                if (shouldAddParentheses(node.getElement(), node.getRightNode().getElement())) {
                    addParentheses(right);
                }

                result.addAll(left);
                result.add(node.getElement());
                result.addAll(right);
                break;
            case POSTFIX:
                // 后缀表达式后序遍历
                result.addAll(ToPrefixOrPostfix(node.getLeftNode(), type));
                result.addAll(ToPrefixOrPostfix(node.getRightNode(), type));
                result.add(node.getElement());
                break;
        }
        return result;
    }

    /**
     * 判断是否需要加上括号
     */
    private static boolean shouldAddParentheses(ExpressionElement element, ExpressionElement rightElements) {
        // 如果右边的节点就是子节点，则不需要加括号
        if (rightElements instanceof NumberElement) {
            return false;
        }

        // 如果右边的表达式优先度小于当前符号，则需要添加括号
        if (getPriority(rightElements) < getPriority(element)) {
            return true;
        }

        // 反之则不需要
        if (getPriority(rightElements) > getPriority(element)) {
            return false;
        }

        // 如果优先度相等，则取决于符号是否为符号或减号
        return element == Calculation.DIVISION || element == Calculation.MINUS;
    }

    /**
     * 给表达式两侧加上括号
     */
    private static void addParentheses(List<ExpressionElement> elements) {
        elements.add(0, LeftParentheses.LEFT);
        elements.add(RightParentheses.RIGHT);
    }

    /**
     * 获取表达式元素的优先度
     */
    private static int getPriority(ExpressionElement element) {
        // 如果不是运算符号，则优先度最高
        if (!(element instanceof Calculation)) {
            return 2;
        }
        return ((Calculation) element).getPriority();
    }
}
